题目分析
这个题目的数据范围是数组长度小于等于1e5,因此我们不能使用$O(n^2)$或者以上时间复杂度的算法进行求解。
哈希表
这个题目和Leetcode第一题非常相似。我们可以设定一个计数器val,当数字出现时,val++,否则val–。一开始val=0。当两次val相同时,说明这中间的字符满足数字和字母相同。
因此我们将计数器第一次出现的位置保存下来,如0号字符是数字,val = 1,那么我们将用map记录一个pair{1, 0},当第8个字符遍历后,发现val = 1。因此我们查看map中已经有了key=1的键值对,我们就可以知道从1号到8号这8个字符中数字和字母是相同的。因为从1号开始val++和val–次数相同。如果长度大于之前保存的最大长度,则替换,如果长度相等,比较起始的字符串的大小。如果小于之前的则替换即可。
此题要注意要给哈希表赋初值,当一个字符都没有时,索引为-1。即map = { {0, -1} },否则在特殊情况下会得到错误结果。如[“A”, “1”],当遍历到第二个元素时,val = 0,发现并没有key = 0的键值对,因此会创建一个{0, 1}的键值对,这就是不正确的。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
刷题总结
两数之和是Leetcode的入坑题,其中包含了非常重要的思想,在今后的做题过程中会反复用到,小伙伴们务必理解它。